이론적 배경: PSPACE-완전과 계산 복잡도

지금까지 우리는 다양한 알고리즘을 통해 끝말잇기 그래프를 분석하고 단순화하여, 게임의 핵심인 '루트 음절' 그래프를 분리해냈습니다. 그렇다면 이 '루트 음절' 영역은 왜 그렇게 분석하기 어려운 것일까요?

그 이유를 이해하기 위해, 우리는 잠시 눈을 돌려 이론 컴퓨터 과학의 계산 복잡도 이론(Computational Complexity Theory)을 살펴볼 필요가 있습니다.

1. 쌍둥이 게임: 일반화된 지리 게임 (Generalized Geography)

컴퓨터 과학에는 끝말잇기와 거의 동일한 규칙을 가진 일반화된 지리 게임(Generalized Geography, GG)이라는 유명한 문제가 있습니다.

• 게임 규칙:
  1. 유향 그래프와 시작 정점이 주어집니다.
  2. 두 플레이어는 번갈아 가며, 현재 정점에서 나가는 엣지를 따라 다른 정점으로 이동합니다.
  3. 한 번 사용된 엣지는 다시 사용할 수 없습니다.
  4. 자신의 턴에 더 이상 움직일 수 없는 플레이어는 패배합니다.

음절을 '정점'으로, 단어를 '엣지'로 본다면, 끝말잇기는 이 일반화된 지리 게임의 한 종류임을 알 수 있습니다.

2. 계산 복잡도의 지도: P, NP, 그리고 PSPACE

컴퓨터 과학자들은 문제의 '어려움'을 여러 등급으로 분류합니다. 가장 대표적인 등급은 P, NP, 그리고 PSPACE입니다.

• P (Polynomial Time): '쉬운 문제'
  컴퓨터가 '빠른 시간' 안에 직접 답을 찾아낼 수 있는 문제들의 집합입니다. 정해진 절차(알고리즘)에 따라 효율적으로 해결할 수 있습니다.

  • 예시: 수천 권의 책을 가나다순으로 정렬하기.

• NP (Nondeterministic Polynomial Time): '검증이 쉬운 문제'
  답을 직접 찾기는 매우 어려울 수 있지만, 누군가 "이것이 답이야"라고 정답을 알려주면 그것이 진짜 정답인지 '빠른 시간' 안에 검증할 수 있는 문제들의 집합입니다.

  • 예시: 거대한 미로 그림에서 '출구로 가는 길이 존재한다'는 것을 증명하기. (길을 찾는 것은 어렵지만, 누군가 그려준 경로가 진짜 출구로 이어지는지 따라가 보는 것은 쉽습니다.)

• PSPACE (Polynomial Space): '시간은 오래 걸려도 괜찮은 문제'
  문제를 푸는 데 필요한 메모리(공간)가 다항식 수준으로 한정된 문제들의 집합입니다. 핵심은 시간 제약이 없다는 점입니다.

  • 예시: 체스 ♟️ 같은 게임이 여기에 해당합니다. 컴퓨터가 최선의 수를 찾기 위해, 한 수를 두고 그 다음 수를 두는 식으로 깊이 탐색을 진행합니다. 이 과정에서 게임 판의 상태를 메모리에 계속 저장합니다. 막다른 길에 도달하면, 방금 뒀던 수를 지우고(메모리에서 이전 상태로 되돌리고) 다른 수를 시도합니다. 이처럼 이길 수 있는 단 하나의 경로를 찾기 위해, 다항 공간이라는 한정된 작업대 위에서 수많은 상태를 저장하고 지우기를 반복하며 탐색을 계속해야 합니다. 필요한 공간은 감당할 수 있지만, 시간은 폭발적으로 늘어날 수 있습니다.

이들의 관계는 P ⊆ NP ⊆ PSPACE 로 알려져 있습니다.

그리고 각 집합에서 가장 어려운 문제들을 '완전(Complete)' 문제라고 부릅니다. 일반화된 지리 게임(GG)은 바로 이 PSPACE-완전 문제라는 사실이 증명되었습니다.

3. 이것이 끝말잇기 분석에 의미하는 것

끝말잇기가 일반화된 지리 게임과 동등하므로, 끝말잇기의 승패를 판별하는 문제 역시 PSPACE-완전입니다. 이 사실은 우리의 분석 전략에 다음과 같은 중요한 통찰을 줍니다.

• 빠른 해법의 부재: "임의의 '루트 음절' 포지션 ($G,v$)가 주어졌을 때, 그 승패를 즉시 알려주는 효율적인 만능 알고리즘은 존재하지 않을 것"이라고 예측할 수 있습니다. 이는 우리가 아직 똑똑한 해법을 찾지 못해서가 아니라, 문제 자체가 본질적으로 그만큼 어렵다는 의미입니다.

• 분석 전략의 정당성: 이 이론적 배경은 왜 우리가 '승패 전파', '루프 분석', '돌림 단어 제거'와 같은 알고리즘들을 사용해야만 했는지 설명해 줍니다. 이러한 알고리즘들의 진정한 가치는, 게임 전체를 한 번에 해결하는 것이 아니라 계산적으로 쉬운 부분을 최대한 걷어내고, 본질적으로 어려운 PSPACE-완전 핵심(루트 음절)만을 정확히 분리해내는 데에 있었던 것입니다.

결론적으로, PSPACE-완전이라는 개념은 끝말잇기 게임의 '루트 음절' 영역이 왜 어려운지에 대한 이론적 근거를 제공하며, 우리가 지금까지 수행해 온 그래프 축소 및 단순화 전략이 매우 합리적이고 올바른 접근이었음을 뒷받침합니다.